package com.chengqs.leetcode.hot100;

import com.chengqs.leetcode.utils.DataGeneratorUtil;
import com.chengqs.leetcode.utils.TimeCostUtil;

/**
 * 普通数组<br>
 * 数组、数学、双指针<br>
 * 中等
 *
 * <h1>189. 轮转数组</h1>
 *
 * <p>给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。</p>
 */
public class E15Rotate {
    public static void main(String[] args) {
        E15Rotate rotate = new E15Rotate();
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int k = 3;

        TimeCostUtil.timeCost("使用额外的数组", () -> rotate.solution1(nums, k));
        TimeCostUtil.timeCost("数组翻转", () -> rotate.solution3(nums, k));

        int[] arr = DataGeneratorUtil.generateRandomIntArray(100000000, -1000, 1000);
        int n = 30000000;
        TimeCostUtil.timeCost("使用额外的数组", () -> rotate.solution1(arr, n));
        TimeCostUtil.timeCost("环状替换", () -> rotate.solution2(arr, n));
        TimeCostUtil.timeCost("数组翻转", () -> rotate.solution3(arr, n));
    }

    // 使用额外的数组
    public void solution1(int[] nums, int k) {
        int length = nums.length;
        int[] newArr = new int[length];
        for (int i = 0; i < length; i++) {
            // 取模运算
            newArr[(i + k) % length] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, length);
    }

    // 环状替换
    public void solution2(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    public int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }

    // 数组翻转
    public void solution3(int[] nums, int k) {
        k %= nums.length;
        // 反转整个数组
        reverse(nums, 0, nums.length - 1);
        // 反转前k个数组
        reverse(nums, 0, k - 1);
        // 反转后k个数组
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}
